package 二叉树;

//222 完全二叉树的节点个数
public class Solution5 {
    //此处是直接深搜遍历了，时间复杂度是O（n）,完全没有用上完全二叉树的特性，面试的时候不考虑这样写
    //或者先写完跑过，然后和面试官说可以优化
//    public int countNodes(TreeNode root) {
//        return dfs(root);
//    }
//    int dfs(TreeNode root){
//        if(root==null){
//            return 0;
//        }
//        return dfs(root.left)+dfs(root.right)+1;
//    }

    int depth;
    public int countNodes(TreeNode root) {
        depth = getDepth(root);
        int l = (int)Math.pow(2, depth-1);
        int r = (int)Math.pow(2, depth)-1;
        //二分
        while(l<r){
            int mid = (l+r+1)/2;
            if(check(root,1,mid,1)){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        return l;
    }
    boolean check(TreeNode node,int cur_index,int target_index,int cur_depth){
        while(cur_depth<depth){
            //当前节点的左边界编号
            int l = cur_index*(int)Math.pow(2, depth-cur_depth);
            //当前节点的右边界编号
            int r = cur_index*(int)Math.pow(2, depth-cur_depth)+(int)Math.pow(2, depth-cur_depth)-1;
            int mid = (l+r)/2;
            if(target_index<=mid){
                cur_index = cur_depth*2;
                if (node.left == null) {
                    return false;
                }
                node=node.left;
            }else {
                cur_index = cur_depth*2+1;
                if(node.right == null) {
                    return false;
                }
                node=node.right;
            }
            cur_depth++;
        }
        //循环出来就到最后一层了，如果不为空那就是true了。或者cur_index==target_index;
        return node!=null;
    }
    int getDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1+getDepth(root.left);//这里不用再计算右子树的高度来取最大高度了，因为是完全二叉树
                                     //要用上完全二叉树的性质
    }

}
